package com.coder.algorithm.leetcode

import com.coder.algorithm.struct.ListNode

/**
 * [234. 回文链表](https://leetcode-cn.com/problems/palindrome-linked-list/)
 *
 * @author yuhus
 * @date: 2022/4/2
 */
object l_0234 {
    /**
     * 反转链表后和原列表对比，事件复杂度 O(n), 空间复杂度 O(n)
     *
     * 进阶：你能否用 `O(n)` 时间复杂度和 `O(1)` 空间复杂度解决此题？
     * 反转一半链表
     */
    fun isPalindrome(head: ListNode?): Boolean {
        if (head?.next == null) {
            return true
        }
        var endOfHalf = endOfHalf(head)
        var secondFirst = reverseList(endOfHalf.next!!)
        var point1: ListNode? = head
        var point2: ListNode? = secondFirst
        while (point1 != null && point2 != null) {
            if (point1.`val` != point2.`val`) {
                return false
            }
            point1 = point1.next
            point2 = point2.next
        }
        endOfHalf.next = reverseList(secondFirst)
        return true
    }

    /**
     * 反转链表
     */
    private fun reverseList(head: ListNode): ListNode {
        var prev: ListNode? = null
        var cur: ListNode? = head
        while (cur != null) {
            val nextNode = cur.next
            cur.next = prev
            prev = cur
            cur = nextNode
        }
        return prev ?: head
    }

    /**
     * 1 -> 2 -> 3 -> 4 -> 5
     * 1 -> 2 -> 3 <- 4 <- 5
     *           |
     *          null
     * 1 -> 2 -> 3 -> 4
     * 1 -> 2 -> 3 <- 4
     *
     * 1,1; 3,2; 5,3;
     * 1,1; 3,2; null,3
     */
    private fun endOfHalf(head: ListNode): ListNode {
        var fast: ListNode = head
        var slow: ListNode = head
        while (fast.next?.next != null) {
            fast = fast.next!!.next!!
            slow = slow.next!!
        }
        return slow
    }
}